//给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。 
//
// 假定 BST 有如下定义： 
//
// 
// 结点左子树中所含结点的值小于等于当前结点的值 
// 结点右子树中所含结点的值大于等于当前结点的值 
// 左子树和右子树都是二叉搜索树 
// 
//
// 例如： 
//给定 BST [1,null,2,2], 
//
//    1
//    \
//     2
//    /
//   2
// 
//
// 返回[2]. 
//
// 提示：如果众数超过1个，不需考虑输出顺序 
//
// 进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内） 
// Related Topics 树 深度优先搜索 二叉搜索树 二叉树 
// 👍 374 👎 0

package com.cute.leetcode.editor.cn;

import com.sun.org.apache.xpath.internal.objects.XNull;
import sun.plugin.javascript.navig.Link;

import java.util.*;

public class FindModeInBinarySearchTree {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode n1 = new TreeNode(2);
        TreeNode n2 = new TreeNode(2);
        root.right = n1;n1.left = n2;
        new FindModeInBinarySearchTree().new Solution().findMode(root);


    }
    public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * 可能不止一个众数
     * 暴力搜索法：最直接的思路：创建一个map，在遍历tree的时候进行次数统计，之后找到map中val的最大值，对应的key就是结果
     * 但是这种方法肯定不是最优解，map遍历了两次，又遍历了一次结果，而且没有利用上二叉搜索树的性质
     *
     * 使用中序遍历，利用二叉搜索树来进行优化：
     * 啊，思路和我一开始想的一样，利用一个前驱节点，一个max，一个count
     * 前驱节点与当前节点相同时count++，如果count>max的时候，需要将结果清空，将max对应的节点加入结果集
     * 如果max==count，将当前结果加入结果集
     *
     * 前驱节点与当前节点不一样的时候直接count = 1,然后将当前结果加入结果集中
     *
     */

    Map<Integer,Integer>map = new HashMap<>();//暴力搜索用
    TreeNode pre = null;//二叉搜索树用
    int max = Integer.MIN_VALUE;
    int count = 0;
    Map<Integer, Integer> newMap = new HashMap<>();

    public int[] findMode(TreeNode root) {
        infixOrder(root);
        int[] res = new int[newMap.size()];
        int i = 0;
        for (int num : newMap.keySet()) res[i++] = num;
        return res;
    }

    public void infixOrder(TreeNode root){
        if (root == null) return;
        infixOrder(root.left);
        if (pre != null && pre.val == root.val){
            count++;
            if (count > max){
                newMap.clear();
                max = count;
                newMap.put(root.val, max);
            }else if (count == max){
                newMap.put(root.val, max);
            }
        }else {
            count = 1;
            newMap.put(root.val, count);
        }
        pre = root;
        infixOrder(root.right);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}